package leetcode_core.sort;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月03日 20:39
 */
public class MergeSort {
    //让[L,R]上的数有序
    public static int process(int[] nums,int L,int R){
        if(L>R){return 0;}
        if(L==R){return 0;}//base-case
        int mid = L+((R-L)>>1);
        return process(nums,L,mid)+
        process(nums,mid+1,R)+
        merge(nums,L,mid,R);
    }
    //双指针方法
    public static int merge(int[] nums,int l,int mid,int r){
        int[] help = new int[r-l+1];
        int k = 0;
        int p1 = l;
        int p2 = mid+1;
        int res = 0;
        while (p1<=mid && p2<=r){
            if(nums[p1]<=nums[p2]){//左边的数比右边的数要小,那么就会产生小和
                res += (r-p2+1)*nums[p1];
                help[k++]=nums[p1++];
            }else {
                help[k++] = nums[p2++];
            }
        }
        while (p1<=mid){
            help[k++] = nums[p1++];
        }
        while (p2<=r){
            help[k++]=nums[p2++];
        }
        //然后将数组的值填到nums
        System.arraycopy(help, 0, nums, l, help.length);
        return res;
    }

}
